#include <stdio.h>

void swap(int a[], int i, int j)
{
	int tmp;
	tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
}

void print(int a[], int len)
{
	int i;
	for (i = 0; i < len; i++)
		printf("%d ", a[i]);
	printf("\n");
}
	
void quiksort(int a[], int len)
{
	int i;
	int last = 0;
	if (len <= 1)
		return;
	swap(a, 0, rand() % len);
	for (i =1; i < len; i++)
	{
		if (a[i] < a[0])
		swap(a, ++last, i);
	}
	printf("%d: ", a[0]);
	swap(a, 0, last);
	print(a, len);
	quiksort(a, last);
	quiksort(a + last + 1, len - last - 1);
}
	
int maopao(int a[], int len)
{
	int i, j, tmp;
	for (i = 0; i < len; i++)
	{
		for (j = 0; j < len -i -1; j++)
		{
			if (a[j] > a[j + 1])
			{
				tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1]= tmp;
			}
		}
	}
	print(a, len);
}

int jiansuo(int a[], int len, int n)
{
	int low, high, mid;
	low = 0;
	high = len - 1;
	while (low < high)
	{
		mid = (low + high) / 2;
		if (n > a[mid])
			low = mid +1;
		else if (n = a[mid])
			return mid;
		else 
			high = mid - 1;
	 
	}
}

int main()
{
	int i, n, len;
	int a[] = {78, 12, 56, 89,14, 93, 15, 66, 21, 91, 95, 100, 77, 71, 99};
	printf("1.冒泡排序\n");
	printf("2.快速排序\n");
	scanf("%d", &n);
	len = sizeof(a) / sizeof(int);
	printf("len: 	%d\n", len);
	switch (n)
	{
		case 1: maopao(a, len);
		break;
		case 2: quiksort(a, len);
		break;
		default: printf("printf error!\n");
		break;
	}
	print(a, len);	
	printf("local: %d, value = %d\n", jiansuo(a, len, 71) - 1, a[jiansuo(a, len, 71) - 1]);
	return 0;
}
